/**
 * 搜索二维矩阵
 *
 * 给你一个满足下述两条属性的 m x n 整数矩阵：
 * 每行中的整数从左到右按非严格递增顺序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
 *
 * 示例 1：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 *
 * 示例 2：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 *
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -104 <= matrix[i][j], target <= 104
 */

/**
 * 两次二分查找
 * 但是我们要注意的是第一次二分查找, 因为第一次二分查找
 * 我们可能查找不到我们想要查找的数字, 这个时候我们会在
 * 两个边界中寻找一个作为我们的行查找开始点, 这个时候我
 * 们需要的是上面一个边界, 所以在使用列二分查找的时候我
 * 们需要注意边界的变化, 在 >= 的时候我们的左边界变更到
 * 这个中间值上来, 后面找到了对应行, 后面的二分就随便了
 * 时间复杂度 : O(log (n))
 * 空间复杂度 : O(1)
 */

public class Main {
    public boolean searchMatrix(int[][] nums, int target) {

        // 矩阵边长
        int m = nums.length, n = nums[0].length;

        // 二分边界
        int left = 0, right = m - 1;


        // 列二分查找
        while (left < right) {

            // 二分中间下标, 这里我们取靠右边的一个, 因为我们需要的是左边界
            // 所以取的时候要取右边界, 避免 = 的时候死循环
            int mid = (right + left + 1) / 2;

            int tmp = nums[mid][0];
            if (target < tmp) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }

        // 找到目标值可能所在的行
        int ret = left;

        // 开始 行 二分查找

        // 这里什么二分查找都可以
        left = 0;
        right = n - 1;
        while (left < right) {
            int mid = (right + left) / 2;
            if (target <= nums[ret][mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        // 最后返回结果看看是否相等
        return nums[ret][left] == target;
    }

    public static void main(String[] args) {
        Main test = new Main();
        int[][] nums = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        test.searchMatrix(nums, 3);
    }
}